import java.util.*;

public class Main {
    public static void main(String[] args) {
        System.out.println("Hello world!");
    }
}

class Solution {
    char[] str = {'A', 'C', 'G', 'T'};
    public int minMutation(String startGene, String endGene, String[] bank) {
        if(startGene.equals(endGene)) return 0;
        Queue<String> queue = new LinkedList<>();
        Set<String> visited = new HashSet<>();//标记已经搜索过的情况
        Set<String> geneIsExist = new HashSet<>();//基因段是否在库里面
        for (String s : bank) {
            geneIsExist.add(s);
        }

        if(!geneIsExist.contains(endGene)) return -1;
        queue.offer(startGene);
        visited.add(startGene);
        int steps = 0;

        while(!queue.isEmpty()){
            int sz = queue.size();
            steps++;
            for(int i = 0; i < sz; i++){
                String poll = queue.poll();
                for (int j = 0; j < 8; j++) {
                    char[] tmp = poll.toCharArray();
                    for (int k = 0; k < 4; k++) {
                        tmp[j] = str[k];
                        String next = new String(tmp);
                        if(!visited.contains(next) && geneIsExist.contains(next)){
                            if(next.equals(endGene)) return steps;
                            queue.offer(next);
                            visited.add(next);
                        }
                    }
                }
            }
        }
        return -1;
    }

}